//四、红黑树的插入
//---------------------------------------------------------
//红黑树的插入结点
rb_node_t* rb_insert(key_t key, data_t data, rb_node_t* root)
{
    rb_node_t *parent = NULL, *node;
 
    parent = NULL;
    /* 调用rb_search_auxiliary找到插入结点的地方 */
    if ((node = rb_search_auxiliary(key, root, &parent))) {
        return root;
    }
 
    node = rb_new_node(key, data);  //分配结点
    node->parent = parent;   
    node->left = node->right = NULL;
    node->color = RED;
 
    if (parent) {
        if (parent->key > key) {
            parent->left = node;
        } else {
            parent->right = node;
        }
    } else {
        root = node;
    }
 
    return rb_insert_rebalance(node, root);   //插入结点后，调用rb_insert_rebalance修复红黑树的性质
}

//五、红黑树的3种插入情况
//接下来，咱们重点分析针对红黑树插入的3种情况，而进行的修复工作。
//--------------------------------------------------------------
//红黑树修复插入的3种情况
//为了在下面的注释中表示方便，也为了让下述代码与我的倆篇文章相对应，
//用z表示当前结点，p[z]表示父母、p[p[z]]表示祖父、y表示叔叔。
//--------------------------------------------------------------
static rb_node_t* rb_insert_rebalance(rb_node_t *node, rb_node_t *root)
{
    rb_node_t *parent, *gparent, *uncle, *tmp;  //父母p[z]、祖父p[p[z]]、叔叔y、临时结点*tmp

    while ((parent = node->parent) && parent->color == RED) {     
        //parent 为node的父母，且当父母的颜色为红时
        gparent = parent->parent;   //gparent为祖父

        if (parent == gparent->left) {
            //当祖父的左孩子即为父母时。
            //其实上述几行语句，无非就是理顺孩子、父母、祖父的关系。:D。
            uncle = gparent->right;  //定义叔叔的概念，叔叔y就是父母的右孩子。
 
            if (uncle && uncle->color == RED) { 
                //情况1：z的叔叔y是红色的
            
                uncle->color = BLACK;   //将叔叔结点y着为黑色
                parent->color = BLACK;  //z的父母p[z]也着为黑色。解决z，p[z]都是红色的问题。
                gparent->color = RED;  
                node = gparent;     //将祖父当做新增结点z，指针z上移俩层，且着为红色。
            //上述情况1中，只考虑了z作为父母的右孩子的情况。
            } else {                     
                //情况2：z的叔叔y是黑色的
               
                if (parent->right == node) {
                //且z为右孩子
                    root = rb_rotate_left(parent, root); //左旋[结点z，与父母结点]
                    tmp = parent;
                    parent = node;
                    node = tmp;     //parent与node 互换角色
                }
                             //情况3：z的叔叔y是黑色的，此时z成为了左孩子。
                                    //注意，1：情况3是由上述情况2变化而来的。
                                    //......2：z的叔叔总是黑色的，否则就是情况1了。
                parent->color = BLACK;   //z的父母p[z]着为黑色
                gparent->color = RED;    //原祖父结点着为红色
                root = rb_rotate_right(gparent, root); //右旋[结点z，与祖父结点]
            }
        } else {
        // if (parent == gparent->right) 当祖父的右孩子即为父母时。（解释请看本文评论下第23楼，同时，感谢SupremeHover指正！）
            uncle = gparent->left;  //祖父的左孩子作为叔叔结点。[原理还是与上部分一样的]
            if (uncle && uncle->color == RED)  //情况1：z的叔叔y是红色的
            {
                uncle->color = BLACK;
                parent->color = BLACK;
                gparent->color = RED;
                node = gparent;           //同上。
            }
            else                               //情况2：z的叔叔y是黑色的，
            {
                if (parent->left == node)  //且z为左孩子
                {
                    root = rb_rotate_right(parent, root);  //以结点parent、root右旋
                    tmp = parent;
                    parent = node;
                    node = tmp;       //parent与node 互换角色
                } 
                  //经过情况2的变化，成为了情况3.
                parent->color = BLACK;
                gparent->color = RED;
                root = rb_rotate_left(gparent, root);   //以结点gparent和root左旋
            }
        }
    }
 
    root->color = BLACK; //根结点，不论怎样，都得置为黑色。
    return root;      //返回根结点。
}